package com.yangli.leecode.mashib.interview;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/13 11:22
 */
public class FortyNine {
    public static void main(String[] args){
        System.out.println(FortyNine.count(new int[]{10, 8, 2, 4, 6, 6, 5}));
        System.out.println(FortyNine.count2(new int[]{10, 8, 2, 4, 6, 6, 5}));

    }

    //求数组种不连续子序列最大==>暴力递归就不演示了，当前位置如果选择就跳下下一个，不选择就跳下一个，返回最大。
    public static int count(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length < 3) {
            return Math.max(arr[0], arr[1]);
        }
        int[] dp = new int[arr.length + 1];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            //arr[i]选择arr[i]是因为有可能为负数，最大值就是当前值
            dp[i] = Math.max(Math.max(arr[i], dp[i - 1]), dp[i - 2] + arr[i]);
        }
        return dp[arr.length - 1];

    }

    //数组变成循环了==>
    public static int count2(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length < 3) {
            return Math.max(arr[0], arr[1]);
        }
        int[] dp1 = new int[arr.length];
        dp1[0] = arr[0];
        dp1[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length - 1; i++) {
            //arr[i]选择arr[i]是因为有可能为负数，最大值就是当前值
            dp1[i] = Math.max(Math.max(arr[i], dp1[i - 1]), dp1[i - 2] + arr[i]);
        }

        int[] dp2 = new int[arr.length];
        dp2[0] = arr[1];
        dp2[1] = Math.max(arr[1], arr[2]);
        for (int i = 2; i < arr.length - 1; i++) {
            //arr[i]选择arr[i]是因为有可能为负数，最大值就是当前值
            dp2[i] = Math.max(Math.max(arr[i + 1], dp2[i - 1]), dp2[i - 2] + arr[i + 1]);
        }
        return Math.max(dp1[arr.length - 2], dp2[arr.length - 2]);
    }
}
